package heap.demo;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description: 优先级队列、堆
 * User: 86187
 * Date: 2022-08-08
 * Time: 11:19
 */

//讲比较器
class Student /*implements Comparable<Student>*/{

    public int age;
    public Student(int age) {
        this.age = age;
    }
    /*@Override
    public int compareTo(Student o) {
        return this.age - o.age;
    }
     */
}
class AgeComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.age - o2.age; //这样是小根堆
         //return o2.age - o1.age; //这样是大根堆
    }
}

public class Test {

    /**
     *堆排序:升序，从小到大排序
     */
    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = { 27,15,19,18,28,34,65,49,25,37};
        testHeap.initArray(array);
        testHeap.createHeap();

        testHeap.heapSort();
        System.out.println();
    }

    /**
     *Top-k 问题: 如求100个数据中k个最大的数据，  求第k大(小)的数据等......
     *  00:46:00 时！！！！
     */

    /**
     * 优化后的Top-k :求100个数据中k个最大的数据， 时间复杂度：n * log k
     */
    private static void top(int[] array,int k,PriorityQueue<Integer> priorityQueue) {
        int i = 0;
        for (; i < k; i++) {
            priorityQueue.offer(array[i]); //入小堆
        }
        while(i < array.length) {
            if(!priorityQueue.isEmpty() && array[i] > priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(array[i]);
            }
            ++i;
        }
        for (int j = 0; j < k; j++) {
            System.out.println(priorityQueue.poll());
        }
    }
    public static void main5(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2; //小堆
                //return o2 - o1; //大堆
            }
        });
        int[] array = {12,45,32,17,2,18,5,10};
        top(array,5,priorityQueue);
        //priorityQueue.offer(1);
    }

    /**
     *未优化的Top-k:求100个数据中k个最大的数据， 时间复杂度: n * log n
     */
    public static void main4(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //return o1 - o2; //小堆
                return o2 - o1; //大堆
            }
        });

        int[] array = {12,45,32,17,2,18,5,10};

        for (int i = 0; i < array.length; i++) {
            priorityQueue.offer(array[i]);
        }

        for (int i = 0; i < 3; i++) {  //假设k的值为3
            System.out.println(priorityQueue.poll());
        }

    }

    /**
     *讲比较器
     */
    public static void main3(String[] args) {
        //注意:1. 插入的数据必须要能够比较，比如此处要告诉它一个比较的规则！！可用比较器！
        //    2.不能插入 null
        //    3. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
        //    4. 插入和删除元素的时间复杂度为 O(logN)
        //    5. PriorityQueue底层使用了堆数据结构, (注意：此处大家可以不用管什么是堆，后文中有介绍)->小根堆
        //    6. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

        Student student1 = new Student(15);
        Student student2 = new Student(5);

        //比较器
        AgeComparator ageComparator = new AgeComparator();
        PriorityQueue<Student> priorityQueue = new PriorityQueue<>(ageComparator); //默认是小根堆
        priorityQueue.offer(student1);
        priorityQueue.offer(student2);

        System.out.println("kkjk");
    }

    public static void main2(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(12);
        priorityQueue.offer(11);
        priorityQueue.offer(42);
        priorityQueue.offer(8);

        System.out.println(priorityQueue.peek());
    }

    /**
     *（大根）堆 模拟 实现 优先级队列
     */
    public static void main1(String[] args) {
         TestHeap testHeap = new TestHeap();
        int[] array = { 27,15,19,18,28,34,65,49,25,37};
        testHeap.initArray(array);

        testHeap.createHeap();
        //testHeap.offer(80);
        System.out.println(testHeap.poll());

        for (int i = 0; i < testHeap.usedSize; i++) {
            System.out.print(testHeap.elem[i]+" ");
        }
    }
}
